第一次做到这种倍增题，有点有趣

首先区间内的每个点对应相等用并查集维护一下就好了，显然最后的答案就是（并查集个数为 $t$） $9 \cdot 10^{t - 1}$

当然这样会造成 $O (n^2)$ 的复杂度，那么通过倍增来优化，即将区间二进制拆分，然后每次将 $[l_1, l_1 + 2^k - 1]$ 与 $[l_2, l_2 +2^k - 1]$ 合并，其中 $k$ 为二进制拆分结果所得幂次的部分，那么这样修改就变成 $O (n \log n)$ 了

对于查询，显然是不能直接查询了，那么就通过由大区间到小区间的传递（即将大区间拆分为左右两段，然后分别与之祖先拆分得左右两段合并）来将信息转移到最小的（即以点为单位的）区间段上

那么最后即 $O (n)$ 查询并查集个数即可

故该倍增整体思想即为：将以点为单位处理改为以幂次区间段为单位处理 $\rightarrow$ 将幂次区间段的信息转移到小区间直至单位区间 $\rightarrow$ 答案处理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;

LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1)
			cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

int N, M;

int father[MAXN][20];
int find (int x, int j) {
	return father[x][j] == x ? x : father[x][j] = find (father[x][j], j);
}
void merge (int x, int y, int j) {
	int fx = find (x, j), fy = find (y, j);
	father[fx][j] = fy;
}
void pushdown () {
	for (int j = 18; j >= 1; j --)
		for (int i = 1; i + (1 << j) - 1 <= N; i ++) {
			int fx = find (i, j);
			merge (i, fx, j - 1);
			merge (i + (1 << (j - 1)), fx + (1 << (j - 1)), j - 1);
		}
}

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	N = getnum (), M = getnum ();
	for (int i = 1; i <= N; i ++)
		for (int j = 0; j <= 18; j ++)
			father[i][j] = i;
	for (int i = 1; i <= M; i ++) {
		int l1 = getnum (), r1 = getnum ();
		int l2 = getnum (), r2 = getnum ();
		int p = 0;
		for (int j = 18; j >= 0; j --)
			if (l1 + p + (1 << j) - 1 <= r1) {
				merge (l1 + p, l2 + p, j);
				p += (1 << j);
			}
	}
	pushdown ();
	int group = 0;
	for (int i = 1; i <= N; i ++)
		if (find (i, 0) == i)
			group ++;
	LL ans = 9ll * power (10ll, group - 1) % MOD;
	cout << ans << endl;

	return 0;
}

/*
4 2
1 2 3 4
3 3 3 3
*/

/*
100000 1
1 99999 2 100000
*/